The Smoothed Particles Hydrodynamics (SPH) method and the Moving Particles Semi-implicit (MPS) method are conventionally known methods of expressing a continuum as distribution of particles, in fluid analysis examining a flow of water or air by using numerical calculations and elastic body analysis examining behavior of compressed rubber. For example, Japanese Laid-Open Patent Publication No. 2008-152423 discloses a technique of numerically analyzing large deformation of a hyperelastic body by using the SPH method. Japanese Laid-Open Patent Publication No. 2010-113467 discloses a technique of performing image deformation by using the MPS method.
These standard particle-based techniques include calculating an interaction from only an opposing particle present in a region (hereinafter referred to as an “influence region”) set in advance for a given particle. Therefore, as a part of the numerical analysis, a process is required for identifying a particle (hereinafter referred to as a “neighbor particle”) in the influence region among the entire region subject to calculation. In modeling of standard particle methods, the influence region is defined as a spherical shape and a numeric value called an influence radius is simply set for each particle.
However, to deal with a state in which a continuum moves in a space while deforming, other techniques are present in which each particle is given a deformation gradient tensor Fij to perform the analysis by using an influence region that is deformed from an original shape by linear transformation. The subscripts i and j of the deformation gradient tensor Fij are indexes indicative of coordinate axes. The deformation gradient tensor Fij is a tensor field given by equation (1), where x denotes initial position coordinates of a continuum and X denotes position coordinates after deformation.Fij=∂Xi/∂xj  (1)
To search for neighbor particles, if proximity is determined with respect each pair of particles, the number of times such determination must be made is proportional to the square of the total number of particles. Since this leads to extremely high calculation cost, a cell index method exists as a technique for accelerating the search for neighbor particles.
The cell index method includes dividing a calculation region into cells of a width equivalent to the influence radius, and searching for a neighbor particle of a given particle i, within the same cell as the given particle i and adjacent cells. If particles are equally distributed in the cells (where, the total number of particles is N), the cell index method requires a calculation amount of O(N) and is faster than the direct method of handling each of the particle pairs and having an calculation amount of O(N2).
Japanese Laid-Open Patent Publication No. 2008-152423 discloses a technique based on the cell index method as a neighbor particle search technique for the SPH method, which has an anisotropic influence region. In this technique, each continuum particle is assumed to belong to a cell of about the size of the influence region and first, a list of neighbor particle candidates common to a particle group included in the cell is created (hereinafter an arbitrary particle group is referred to as a “particle group i”; an individual particle included in the particle group i is referred to as an “i-particle”).
The neighbor particle candidate list generally includes the particle group i. Whether a particle included in this list and a particle of the particle group i are neighbor particles is individually judged for each of pair of particles. Therefore, when Ni is the number of particles included in the particle group i and Nj is the number of particles included in the neighbor particle candidate list, the number of times that comparison must be performed is O(NiNj) per cell. Thus, if the number of particles included in the neighbor particle candidate list can be reduced, the cost required for the neighbor particle search can be reduced.
In the Astrophysical Journal Supplement Series 1998, 116, pp. 208-209, (Appendix C3), Owen, Villumsen, Shapiro, and Martel propose to reduce the number of particles of the neighbor particle candidate list by taking deformation of an influence region into consideration. For example, the following procedure is utilized.
First, the minimum value and the maximum value of coordinates of the i-particles are examined and referred to as ximin and ximax, respectively. These values are set for each coordinate axis to construct a minimum space Si that includes the entire particle group i (a rectangle in a two-dimensional case or a rectangular parallelepiped in a three-dimensional case). The minimum/maximum coordinates of the influence region, which may be deformed, of the i-particles are obtained and defined as xihmin and xihmax, respectively. These coordinates are set for each coordinate axis. A space Shi (a rectangle in a two-dimensional case or a rectangular parallelepiped in a three-dimensional case) is set from xihmin, and xihmax.
The space Shi encompasses the space Si; and a particle included in the influence region of the i-particles is always included in the space Shi. Therefore, if a given particle j1 is included in the space Shi, the particle j1 is added to the neighbor particle candidate list. As a result, the number of particles included in the neighbor particle candidate list is reduced with consideration that the degree of deformation differs for each coordination axis.
On the other hand, even if a given particle j2 is outside the space Shi, the influence region of the particle j2 may include a particle i. In such a case, if a rectangle (or a rectangular parallelepiped) circumscribed by the influence region of the particle j2 and the space Shi have a common region, the particle j2 is also added to the neighbor particle candidate list.
Nonetheless, with the conventional techniques, if a particle has an influence region highly deformed in an oblique direction relative to a coordinate axis, the particle is added to the neighbor particle candidate list when the circumscribed rectangle (or rectangular parallelepiped) overlaps though the influence region does not overlap. Therefore, the neighbor particle candidate list includes more particles than necessary, thereby reducing search accuracy and causing a problem of an increased calculation load.